package com.剑指offer.第七章队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入一颗二叉树、请找出二叉树中的每层最大值。
 * <p>
 * 使用队列 广度优先
 * <p>
 * 由于要找出二叉树中每层的最大值，因此在遍历时需要知道每层什么时候开始遍历，什么时候结束
 * <p>
 * 可以通过计数的方式
 * <p>
 * 可以用两个变量分别记录两层节点的数目，变量current记录当前这一层中位于队列之中节点的数据，变量next记录下一层中位于队列之中节点的数目
 * <p>
 * 当从队列中取出一个节点，current -1 存在左右子节点，分别+1 当current=0时，说明 这一层结束  current=next，next=0，
 */
public class 二叉树中每层的最大值 {

    public static List<Integer> resolve(TreeNode root) {
        int current = 0;
        int next = 0;

        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        if (root != null) {
            current = 1;
            treeNodes.offer(root);
        }

        List<Integer> result = new ArrayList<>();
        Integer max = Integer.MIN_VALUE;
        while (!treeNodes.isEmpty()) {
            TreeNode poll = treeNodes.poll();
            current--;

            max = Math.min(max, poll.val);

            if (poll.left != null) {
                treeNodes.offer(poll.left);
                next++;
            }

            if (poll.right != null) {
                treeNodes.offer(poll.right);
                next++;
            }

            if (current == 0) {
                result.add(max);
                max = Integer.MIN_VALUE;
                // 开启下一次记录
                current = next;
                next = 0;
            }

        }

        return result;
    }

}
